package Leetcode第一期;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 *  
 *
 * 例如，给出
 *
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 * 返回如下的二叉树：
 *
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *  
 */
public class 重建二叉树_7 {
    private Map<Integer, Integer> reverses;
    private int[] preorder;

    //方法一
    //递归方法 传入数组拷贝
    public TreeNode buildTreeA(int[] pre, int[] in) {
        if(pre==null||in==null||pre.length==0||in.length==0){return null;}

        if (pre.length != in.length){return null;}

        TreeNode root=new TreeNode(pre[0]);//根节点
        for (int i=0;i<pre.length;i++){
            if (pre[0]==in[i]){
                root.left=buildTreeA(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right=buildTreeA(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return root;
    }

    //方法二
    //递归 传入数组边界索引
    private TreeNode buildTree(int preL, int preR,int inL, int inR) {
        if(preL>preR||inL>inR){
            return null;
        }
        //前序数组作为根,取得节点得值
        int pivot=preorder[preL];
        TreeNode root=new TreeNode(pivot);
        //查找前序数组中根节点在 中序数组中的位置（索引值）  优化：代替了遍历
        int pivotIndex=reverses.get(pivot);
        root.left=buildTree(preL+1,preL+(pivotIndex-inL),inL,pivotIndex-1);
        root.right=buildTree(preL+(pivotIndex-inL)+1,preR,pivotIndex+1,inR);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int inLen = inorder.length;
        this.preorder = preorder;
        //将中序数组放入hashmap，用于后续判断。
        reverses = new HashMap<>(inLen);
        for (int i = 0; i < inorder.length; i++) {
            reverses.put(inorder[i], i);
        }
        return buildTree(0, preLen - 1, 0, inLen - 1);
    }

    //复习方法一
    //递归 传入数组边界索引（练习回顾）
    public TreeNode buildTreeB (int[] pre, int[] in) {
        if(pre==null||in==null||pre.length==0||in.length==0){return null;}
        if (pre.length != in.length){return null;}

        return helper(pre,0,pre.length-1,in,0,in.length-1);
    }

    private TreeNode helper(int[] pre, int preL, int preR, int[] in, int inL, int inR) {
        if(preL>preR||inL>inR){return null;}
        int rootVal=pre[preL];
        int index =0;

        while (index<=inR && in[index] != rootVal){
            index++; //找到根索引
        }

        TreeNode root=new TreeNode(rootVal);
        root.left=helper(pre,preL+1,preL-inL+index,in,inL,index);
        root.right=helper(pre,preL-inL+index+1,preR,in,index+1,inR);
        return root;
    }


    //方法三
    //迭代
    public  TreeNode buildTreeC(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int length = preorder.length;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        int[] a={3,9,2,5,20,15,7};
        int[] b={2,9,5,3,15,20,7};
        new 重建二叉树_7().buildTreeC(a,b);
    }

}
